#include "LinkTree.h"
#include <iostream>

TreeNode::TreeNode(const ElementType &element)
{
    data = element;
    parent = nextSbling = firstChild = nullptr;
}

void TreeNode::Connect(TreeNode *parent)
{
    if(!parent)
        return;

    this->parent = parent;

    this->nextSbling = parent->firstChild;
    parent->firstChild = this;
}

void TreeNode::Disconnect(TreeNode *parent)
{
    if(parent == nullptr && this->parent != parent)  //不是同一个父节点
        return;

    TreeNode *travelPoint = parent->firstChild;  //遍历指针
    if(this == parent->firstChild)  //是第一个孩子
    {
        parent->firstChild = this->nextSbling;
    }
    else
    {
        while(travelPoint->nextSbling != nullptr)
        {
            if(travelPoint->nextSbling == this)
            {
                travelPoint->nextSbling = this->nextSbling;
                break;
            }
            travelPoint = travelPoint->nextSbling;
        }
    }
    this->parent = this->nextSbling = nullptr;
}

LinkTree::LinkTree()
{
    root = new TreeNode(nullptr);
    Free = nullptr;
    Compare = nullptr;
    Print = nullptr;
    CopyData = nullptr;
}

LinkTree::~LinkTree()
{
    FreeNode(root);
}

void LinkTree::show()
{
    show(root,-1);
}

DoubleLinkList LinkTree::FindByElement(const ElementType &element)
{
    DoubleLinkList list;
    FindNode(root, element, list);
    return list;
}

int LinkTree::GetTreeHeight()
{
    return GetNodeHeight(root) - 1;  //根节点不算高度
}

int LinkTree::Size()
{
    int count = 0;
    GetNodeSize(root, count);  //根节点也算一个结点
    return count - 1;
}

int LinkTree::Count()
{
    int count = 0;
    GetNodeCount(root, count);
    return count;
}

int LinkTree::GetNodeHeight(TreeNode *node)
{
    if(node == nullptr)
        return 0;
    int MaxHeight = 0;
    TreeNode *travelPoint = node->firstChild;  //遍历指针
    while(travelPoint != nullptr)
    {
        int NodeHeight = GetNodeHeight(travelPoint);  //递归获取子树高度
        MaxHeight = MaxHeight > NodeHeight ? MaxHeight : NodeHeight;  //获取最大高度
        travelPoint = travelPoint->nextSbling;  //遍历兄弟节点
    }
    return MaxHeight + 1;  //加上当前节点的高度
}

void LinkTree::GetNodeSize(TreeNode *node, int &count)
{
    if(node == nullptr)
        return ;
    count++;
    GetNodeSize(node->firstChild, count);
    GetNodeSize(node->nextSbling, count);
}

void LinkTree::GetNodeCount(TreeNode *node, int &count)
{
    if(node == nullptr)
        return ;
    if(node->firstChild == nullptr)
        count++;
    GetNodeCount(node->firstChild, count);
    GetNodeCount(node->nextSbling, count);
}

void LinkTree::FindNode(TreeNode *node, const ElementType &element, DoubleLinkList &list)
{
    if(node == nullptr)
        return;
    if(node->data == element && node != root)
        list.InsertTail(node);
    FindNode(node->firstChild, element, list);
    FindNode(node->nextSbling, element, list);
}

void LinkTree::show(TreeNode *node, int deepth)
{
    if(node == nullptr)
        return;
    if(node->parent != nullptr)  //不是根节点才打印
    {
        if(deepth > 0)
        {
            for(int i = 0; i < deepth; i++)
            std::cout<<"    ";
            std::cout<<"|___";
        }
        //std::cout<<node->data<<std::endl;
        Print(node->data);
    }
        
    //深度优先遍历
    show(node->firstChild, deepth + 1);
    show(node->nextSbling, deepth);

    //广度优先遍历
    // show(node->nextSbling,deepth);
    // show(node->firstChild, deepth + 1);
}

void LinkTree::FreeNode(TreeNode *node)
{
    if(node == nullptr)
        return;
    FreeNode(node->firstChild);
    FreeNode(node->nextSbling);
    //std::cout<<"delete "<<node->data<<std::endl;
    if(this->Free != nullptr)
        this->Free(node->data);
    delete node;
}



